import java.util.HashMap;

/**
 * @author 汤奇
 * @version V1.0
 * @Project BookPro
 * @Package PACKAGE_NAME
 * @Description:
 * @Date 2022/7/27 20:35
 */
public class Test14 {
    /**
     * 走阶梯，有n级阶梯，一次可以走一级、两级或者三级，请编写一个函数计算走完该阶梯一共有多少种方法
     * 请写出优化后的答案。
     * @param args
     */
    public static void main(String[] args) {
        long strart = System.currentTimeMillis();
        System.out.println(f1(50));
        long end = System.currentTimeMillis();
        System.out.println("耗时:"+(end-strart));
    }

    private static long f(int n){
        if (n == 1)
            return 1;

        if (n == 2)
            return 2;

        if (n == 3)
            return 4;

        return f(n-1)+f(n-2)+f(n-3);
    }

    /**
     * 循环
     * @param n
     * @return
     */
    private static long f1(int n){
        if (n == 1)
            return 1;

        if (n == 2)
            return 2;

        if (n == 3)
            return 4;
        long a = 1;
        long b = 2;
        long c = 4;
        long d = 0;
        for (int i = 0; i < n - 3; i++) {
            d = a+b+c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }

    /**
     * 缓存表
     */
    private static HashMap<Integer,Long> cache = new HashMap<>();
    private static long f2(int n){
        if (n == 1)
            return 1;

        if (n == 2)
            return 2;

        if (n == 3)
            return 4;

        if (cache.get(n) != null){
            return cache.get(n);
        } else {
            long result = f2(n-1)+ f2(n-2)+f2(n-3);
            cache.put(n,result);
            return result;
        }
    }

}
